#!/depot/perl-5.6.1/bin/perl

############################################################
# Title : Guess Number
#-----------------------------------------------------------
# By    : Sean Zhang
# At    : Apr, 2006
# @     : szhang@synopsys.com
############################################################

if($ARGV[0] !~ /^\d\d\d\d$/){
    print <<__HELP__;
  Usage: $0 [\d\d\d\d]
   e.g.: $0 9837

__HELP__
    exit(1);
}

#my @target = (9,3,8,1);
my @target = split(//,$ARGV[0]);
my @try = ();
my @pool = ([0..9],[0..9],[0..9],[0..9]);
my @answer = ();

%ns = init();
#print join("\n",@ns);

my $loop = 0;
while(1){
    $loop ++;
    $try = get_min();
    @try = split(//,$try);
    @answer = check_number(\@try,\@target);
    @ns = keys %ns;
    print sprintf("Loop %02d [%4d] | ", $loop, $#ns+1), join(" ",@try)," | ",join(" ",@answer),"\n";
    last if $answer[0] == 4 || $loop > 15;
    foreach my $t (keys %ns) {
	my @t = split(//,$t);
	my ($n_match,$n_has) = check_number(\@try,\@t);
	if($n_match == $answer[0] && $n_has == $answer[1]){
	}else{
	    delete $ns{$t};
	}
    }
}


exit;


#--------------------------------------------------------------------------

sub get_min {
    #TODO: need improvements here
    #TODO: need a way to avoid pick the similar number
    my @ns = sort {$ns{$a} <=> $ns{$b}} keys %ns;
    return $ns[0];
}

sub init{
    my %ns = ();
    foreach my $n (0000..9999){
        my @n = split(//,$n);
        my %cnt = ();
        my $skip = 0;
        foreach my $i (@n) {
            if(exists($cnt{$i})){
                $skip = 1;
            }
            $cnt{$i} = 1;
        }
        next if $skip ;
        $n = sprintf("%04d",$n);
        $ns{$n}=0;
    }    
    return %ns;
}


sub check_number {
    my ($try,$target) = @_;
    my @try = @$try;
    my @target = @$target;
    my ($n_exact,$n_has ) = (0,0);
    foreach my $i (0..$#try) {
        my $number = $try[$i];
        foreach my $j (0..$#target){
	    if($number == $target[$j]) {
                if($i == $j){
		    $n_exact ++;
                }else{
		    $n_has ++;
                }
	    }
        }
    }
    return ($n_exact,$n_has);
}

